package offer2

/*
原题链接:
https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/

剑指offer 14_2.剪绳子Ⅱ
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
每段绳子的长度记为 k[0],k[1]...k[m - 1] 。
请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？

例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1

	输入 2
	输出 1
	解释 2 = 1 + 1, 1 × 1 = 1

示例 2

	输入 10
	输出 36
	解释 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
*/

func cutRope(number int64) int64 {
	if number == 1 || number == 2 {
		return 1
	}
	if number == 3 {
		return 2
	}

	if number%3 == 0 {
		return QuicPow(number / 3)
	}
	if number%3 == 1 {
		return 4 * QuicPow(number/3-1) % 998244353
	}
	if number%3 == 2 {
		return 2 * QuicPow(number/3) % 998244353
	}

	return 0
}

func QuicPow(n int64) int64 {
	if n == 0 {
		return 1
	}
	if n == 1 {
		return 3
	}

	if n%2 == 0 {
		half := QuicPow(n / 2)
		return half * half % 998244353
	} else {
		half := QuicPow(n / 2)
		return 3 * half * half % 998244353
	}

}
